class Tree:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None
        self.lis = []

    def preface(self, node):
        '''先序'''
        self.lis.append(node.data)
        if node.left != None:
            self.preface(node.left)
        if node.right != None:
            self.preface(node.right)

    def middleorder(self, node):
        '''中序'''
        if node.left != None:
            self.middleorder(node.left)

        self.lis.append(node.data)

        if node.right != None:
            self.middleorder(node.right)

    def postscript(self, node):
        '''后序'''
        if node.left != None:
            self.postscript(node.left)
        if node.right != None:
            self.postscript(node.right)

        self.lis.append(node.data)

    def search(self, node, lis, data):
        '''查找'''
        if not node.left == None:
            lis = self.search(node.left, lis, data)

        if not node.right == None:
            lis = self.search(node.right, lis, data)

        if lis != []:
            # 判断当前节点是否在查询节点的线上
            
            if node.left != None:
                if lis[-1] == node.left.data:
                    lis.append(node.data)

            if node.right != None:
                if lis[-1] == node.right.data:
                    lis.append(node.data)

        if node.data == data:
            lis.append(data)

        return lis


if __name__ == '__main__':
    root = Tree()

    root.data = 'A'

    root.left = Tree()
    root.left.data = 'B'

    root.right = Tree()
    root.right.data = 'C'

    root.left.left = Tree()
    root.left.left.data = 'D'

    root.right.left = Tree()
    root.right.left.data = 'E'

    root.right.right = Tree()
    root.right.right.data = 'F'

    root.left.left.left = Tree()
    root.left.left.left.data = 'G'

    root.left.left.right = Tree()
    root.left.left.right.data = 'H'

    root.right.left.right = Tree()
    root.right.left.right.data = 'I'

    print('先序:')
    root.lis = []
    root.preface(root)
    print(root.lis)
    print('中序:')
    root.lis = []
    root.middleorder(root)
    print(root.lis)
    print('后序:')
    root.lis = []
    root.postscript(root)
    print(root.lis)

    print(root.search(root, [], 'H')[::-1])
